package com.year_23.april;

/**
 *
 * 1043 分隔数组以得到最大值
 *      https://leetcode.cn/problems/partition-array-for-maximum-sum/
 *
 *      动态规划
 * @Author jsh
 * @Date 2023/4/19 22:12
 * @Version 1.0
 */
public class Day19 {

    public static void main(String[] args) {
        int[] arr = {1,15,7,9,2,5,10};

        System.out.println(maxSumAfterPartitioning(arr, 3));
    }
    public static int maxSumAfterPartitioning(int[] arr, int k) {
        int l = arr.length;
        int[] dp = new int[l + 1];
        for (int i = 1; i <= l; i++) {
            int maxv = arr[i - 1];
            for (int j = i -1; j >= 0 && j >= i - k ; j--) {
                dp[i] = Math.max(dp[i], dp[j] + maxv * (i - j));
                if (j > 0){
                    maxv = Math.max(maxv, arr[j - 1]);
                }
            }
        }
        return dp[l];

    }
}
